//
// Created by 高森森 on 2022/2/13.
//

#ifndef LEETCODE_SOLUTION39_H
#define LEETCODE_SOLUTION39_H
#include<iostream>
#include<vector>
#include <memory.h>

using namespace std;

class Solution39 {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        int n=graph.size();
        int memo[2*50*50][50][50];
        memset(memo,-1,sizeof(memo));
        return dfs(0,1,2,n,graph,memo);
    }
    int dfs(int k,int a,int b,int n,vector<vector<int>>&graph,int memo[][50][50]){
        int ans=memo[k][a][b];
        if(a==0) ans= 1;//老鼠获胜
        else if(a==b)ans=2;//猫获胜
        else if(k>=2*n*n) ans= 0;//平局
        else if(ans==-1){
            //老鼠走
            if(k%2==0){
                //老鼠先走 win设置最坏的结果败 draw设置是否平局
                bool win=false;
                bool draw= false;
                for(auto &ne:graph[a]){
                    int t=dfs(k+1,ne,b,n,graph,memo);
                    if(t==0) draw= true;
                    else if(t==1)
                    {
                        win= true;
                        break;
                    }

                }
                if(win)
                    ans=1;
                else if(draw) ans=0;
                else ans=2;
            }
            else{
                //猫走
                bool  win=false;
                bool draw= false;
                for(auto ne:graph[b]){
                    if (ne == 0) continue;
                    int t=dfs(k+1,a,ne,n,graph,memo);
                    if(t==0) draw= true;
                    else if(t==2){
                        win= true;
                        break;
                    }
                }
                if(win)
                    ans=2;
                else if(draw)
                    ans=0;
                else
                    ans=1;

            }
        }
        memo[k][a][b]=ans;
        return ans;
    }
};


#endif //LEETCODE_SOLUTION39_H
